package kechengsheji;

import MGraph.LinkedGraph;

public class shortestpath {
    boolean[][] P;
    int[] D;
    final static int INFINITY = 1000;
    public void DIJ(LinkedGraph G, int v0){
        int VexNum = G.getVexNum();
        P = new boolean[VexNum][VexNum];
        D = new int[VexNum];
        boolean[] finish = new boolean[VexNum];
        for(int v=0;v<VexNum;v++){
            finish[v] = false;
            D[v] = (int)G.getArcs()[v0][v];
            for(int w=0;w<VexNum;w++)P[v][w] = false;
            if(D[v]<INFINITY){P[v][v0]=true;P[v][v]=true;}
        }
        D[v0]=0;
        finish[v0]=true;
        int v=-1;
        for(int i=1;i<VexNum;i++){
            int min = INFINITY;
            for(int w = 0;w<VexNum;w++)
                if(!finish[w])if(D[w]<min){v=w;min=D[w];}
            finish[v]=true;
                for(int w = 0;w<VexNum;w++)
                    if(!finish[w]&&(int)G.getArcs()[v][w]<INFINITY&&(min+(int)G.getArcs()[v][w]<D[w])){
                        D[w]=min+(int)G.getArcs()[v][w];
                        System.arraycopy(P[v],0,P[w],0,P[v].length);
                        P[w][w]=true;
                    }
        }
    }
    public int[] getD(){
        return D;
    }
    public boolean[][] getP(){
        return P;
    }

}
